package zijie;

import java.util.ArrayList;
import java.util.List;

public class ThreeSum_15_10 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 3) return res;
        quickSort(nums,0,nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0){
                return res;
            }

            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while (right > left && nums[right] == nums[right-1]){
                        right--;
                    }
                    while (right > left && nums[left] == nums[left + 1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }

        return res;
    }

    public void quickSort(int[] nums,int left,int right){
        if(left >= right){
            return ;
        }
        int base = partition(nums,left,right);
        quickSort(nums,left,base - 1);
        quickSort(nums,base + 1,right);

    }

    public int partition(int[] nums, int l,int r){
        int base = nums[l];
        int left = l;
        int right = r;
        while (left != right){
            while (left < right && nums[right] > base){
                right--;
            }
            while (left < right && nums[left] <= base){
                left++;
            }
            if(left < right){
                int tmp = nums[right];
                nums[right] = nums[left];
                nums[left] = tmp;
            }
        }
        nums[l] = nums[left];
        nums[left] = base;
        return left;
    }

    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        if(nums.length < 3) return res;
        quickSort2(nums,0,nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0){
                return res;
            }

            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while (right > left && nums[right] == nums[right-1]){
                        right--;
                    }
                    while (right > left && nums[left] == nums[left + 1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return res;
    }

    private void quickSort2(int[] nums, int left,int right){
        if(left >= right){
            return;
        }
        int base = partition2(nums,left,right);
        quickSort2(nums,left,base - 1);
        quickSort2(nums,base+1,right);



    }

    public int partition2(int[] nums, int l,int r){
        int base = nums[l];
        int left = l;
        int right = r;
        while (left < right){
            while (left < right && nums[right] > base){
                right--;
            }
            while (left < right && nums[left] <= base){
                left++;
            }
            if(left < right){
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
            }
        }
        int temp2 = nums[left];
        nums[left] = base;
        nums[l] = temp2;
        return left;
    }




    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        ThreeSum_15_10 threeSum_15 = new ThreeSum_15_10();
        List<List<Integer>> lists = threeSum_15.threeSum(nums);
        System.out.println(lists);
    }
}
